package tools;

import java.util.List;
import datatypes.Edge;
import datatypes.Vertex;

/**
 * Test LMT triangulation if all Ponts are connected
 * 
 * Note: this code is complete and awaits to be tested in working environment. Rev 9.08.2011:
 * 
 * This algorithm sets all points white, and progressively colors them first
 * gray, and after successfully checked all its sucessors: black. On algorithm
 * completion, all points must be colored black, otherwise the graph is not
 * connected.
 * 
 * Graph`s points are characterised by state, where:
 * 
 * white 	- point not visited; if it remains white, graph is *not* connected
 * gray 	- point in progress: *not* all its successors has been visted yet. 
 * black 	- point is complete: point and all its successors has been visited.
 * 
 * 
 * usage: DepthFirstSearch dfs = new DepthFirstSearch(pointlist, edgeList);
 * 		  boolean connected = dfs.isAllConnected();
 * 
 * @author ltune
 * 
 * Source: This algorithm implementation depends on the following code:
 * 
 * http://www.algolist.net/Algorithms/Graph/Undirected/Depth-first_search
 * 
 */
public class DepthFirstSearch {

	/**
	 * The three states an point can be colored, according to the algorithm
	 * 
	 * @author ltune
	 * 
	 */
	enum VertexState {
		White, Gray, Black
	}

	/**
	 * Conttructor for DFS-check pass graph as V and E lists
	 * 
	 * */
	public DepthFirstSearch(List<Vertex> pointList, List<Edge> edgesArray) {
		super();
		this.pointList = pointList;
		this.edgesArray = edgesArray;
		this.vertexCount = edgesArray.size();
	}

	/* member variables for DFS search */
	private int vertexCount; // number of edges
	private VertexState[] state; // points state
	private List<Vertex> pointList; // represents the grpaghs' points
	private List<Edge> edgesArray; // represents the graphs' edges

	/* end DFS variables */

	/* getters and setters */

	public List<Vertex> getPointList() {
		return pointList;
	}

	public void setPointList(List<Vertex> pointList) {
		this.pointList = pointList;
	}

	public List<Edge> getEdgesArray() {
		return edgesArray;
	}

	public void setEdgesArray(List<Edge> edgesArray) {
		this.edgesArray = edgesArray;
	}


	/* end gettes and setters */

	public void resetEdges() {
		state = new VertexState[vertexCount];

		for (int i = 0; i < vertexCount; i++)
			state[i] = VertexState.White;
	}

	public void runDFS(int u, VertexState[] state)	{
		state[u] = VertexState.Gray;
		for (int v = 0; v < vertexCount; v++) {
			if (isEdge(u, v) && state[v] == VertexState.White)
				runDFS(v, state);
		}
		state[u] = VertexState.Black;
	}

	/**
	 * check if two points u,v are connected by an edge
	 * 
	 * @param u - point currently checked
	 * @param v - candidate point checked
	 * 
	 * @return true, if u is directly connected to v, false otherwise
	 */
	private boolean isEdge(int u, int v) {
		for (int i = 0; i < edgesArray.size(); i++) {
			// check if u and v are connected by an edge, by iterating over all edges.
			if( (pointList.get(u).getX() == edgesArray.get(i).getVertex1().getX()) &&
					(pointList.get(u).getY() == edgesArray.get(i).getVertex1().getY()) &&
					(pointList.get(v).getX() == edgesArray.get(i).getVertex2().getX()) &&
					(pointList.get(v).getY() == edgesArray.get(i).getVertex2().getY())){
				// ALLRIGHT! We found an edge that connects u to v, so return true!
				return true;
			}
		}
		return false;
	}

	/**
	 * This is the DFS' heart, note it is not yet ready. Now, you can ,howerver,
	 * check, whether all your points are connected by at least one Edge or not.
	 * (ie: Whether all Point are connected at all)
	 * 
	 */
	public boolean isAllConected() {
		resetEdges(); // set all point white
		runDFS(0, state); // bring it on, by envoking the DFS algorithm
		// check if all point are black, otherwise graph not connected	
			checkpoint: for (int i = 0; i < state.length; i++) {
					// point is connected to an eges so continue
				if(state[i] == VertexState.Black){
					continue checkpoint;
				}
			// OH NO! WE found a not connected point
			return false;
		}
		// OK! WE have checked and all Points are connected! GOOD Work
		return true;
	}
}
